package org.yh.demo.algorithm;

import java.util.Stack;

public class StackPushPopTest {

    public static boolean  validateStackSequences(int[] pushed, int[] popped) {
        if(pushed == null || popped == null || pushed.length == 0 || pushed.length == 0){
            return true;
        }

        int length = popped.length;

        Stack<Integer> stack = new Stack();
        int i=0,j=0;
        for(;j < length || i < length;){
            int top = stack.empty()?-1:stack.peek();
            if(j>= length){
                if(top == popped[i]){
                    stack.pop();
                    i++;
                }else {
                    return false;
                }
            }else {
                if (popped[i] != pushed[j] && top != popped[i]) {
                    stack.push(pushed[j]);
                    j++;
                } else if (top == popped[i]) {
                    stack.pop();
                    //j++;
                    i++;
                } else {
                    j++;
                    i++;
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(validateStackSequences(new int[]{2,3,0,1}, new int[]{0,3,2,1}));
    }
}
